#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

'''
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组 的小和
'''

def conquer(arr: list, pl: int, mid: int, pr: int) -> int: 
    aux = []
    l = pl
    r = mid + 1
    res = 0

    while l <= mid and r <= pr:
        if arr[l] < arr[r]:
            res += arr[l] * (pr - r + 1)
            aux.append(arr[l])
            l += 1
        else :
            aux.append(arr[r])
            r += 1
    while r <= pr:
        aux.append(arr[r])
        r += 1
    while l <= mid:
        aux.append(arr[l])
        l += 1
    arr[pl: pr+1] = aux[:]
    return res

def d_c_sort(arr: list, pl: int, pr: int) -> int:
    
    if pl >= pr : return 0 
    mid = pl + ((pr - pr) >> 1)

    return  d_c_sort(arr, pl, mid) +\
        d_c_sort(arr, mid + 1, pr) +\
            conquer(arr, pl, mid, pr)

def small_sum(arr: list)->int:
    if not arr or len(arr) < 2: return 0
    
    return d_c_sort(arr, 0, len(arr) -1)

def compare(arr: list) -> int:
    if not arr or len(arr) < 2: return 0
    res = 0
    for i in range(1, len(arr)):
        for j in range(0, i):
            if arr[j] < arr[i]:
                res += arr[j]
    return res   

import random

def generate_random_array(max_size: int, max_value: int) -> list:
    length = random.randint(1, max_size )  #random.randint结果包括右边界
    arr = []
    for i in range(length):
        arr.append(random.randint(1, max_value))
    return arr

def copy_array(arr : list) -> list:
    if len(arr) == 0 : return None
# list2 = list1.copy()
    return arr[:]

def print_array(arr : list) :
    if not arr: return
    print(arr)

def bubble_sort(arr : list):
    n = len(arr)
    if not arr or n < 2 :
        return
    for i in range(n - 1):   #总共循环n-1
        flag = 0
        for j in range(n - i -1):  #每次循环预留最后一个不做比较
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                flag = 1
        if flag == 0 : break
    return

def main():
    test_time = 500000
    max_size = 100
    max_value = 100
    succeed = True
    for i in range(test_time):
        arr1 = generate_random_array(max_size, max_value)
        arr2 = copy_array(arr1)

        if small_sum(arr1) != compare(arr2):
            succeed = False
            break

    print('Nice!' if succeed else 'Fucking fucked!')

    if succeed is False:
        print("small_sum\n")
        print_array(arr1)
        print("compare\n")
        print_array(arr2)

if __name__ == "__main__":
     main()